演化計算：有指引的隨機搜尋

演化計算（Evolutionary Computation）算是這幾年逐漸成熟的新學門，屬於「人工智能 Artificial Intelligence」（或計算智能 Computational Intelligence）的子領域，主要與組合最佳化（Combinatorial Optimization）有關。

要細說這類演算法，不太容易在很短的篇幅裡做到，但是透過「爬山算法」（Hill Climbing）的例子，倒是不難瞭解這類演算法與傳統方法的不同之處。

 在電腦計算上，常常需要處理「最佳化」的問題，把這樣的問題圖形化，就好比是在附圖裡面尋找最高（或最低）點。當然這是簡化的情況，一般來說會動用到演化計算的最佳化問題，都不會只有一個變項，但是這並不妨礙我們用這個例子來說明。

要在這張圖上找最高點，最簡單的搜尋方法是「爬山算法」：在目前所在的位置上，看是左邊比較高，還是右邊比較高，然後往比較高的地方移動一小步；如此反覆進行，直到左右都不比現在高為止。這種算法雖然簡便快速，但很容易遇到問題：只能爬到局部的最高點。

以上圖為例，如果從 3.6～4.7 之間開始爬山，最後定會爬到 4.12 的局部高點，而不是 6.64 的最高點。事實上，除非開始爬山的位置在 6～7.3 之間，否則都只會找到局部的小山頭。

因此，要避免卡在「局部最佳值」上，必須要修正這個爬山算法。

最簡單的修正法，是從多個點開始爬山，然後選取每個山頭當中最高的那座。這些點的選取，最好完全是隨機分布的，這個取向最後通往著名的 Markov chain Monte Carlo (MCMC) 方法，可以說是隨機的隨機，細節在此先略過不表。

演化算法也是從多個點開始嘗試爬山，第一代根據隨機決定起始點的爬山結果，再進行下一次的抽樣，但是接下來的抽樣已經不是完全的隨機，而是由前一「代」的爬山結果來指引的。這應該稱呼為「被引導的隨機」，根據實驗，這個方法通常會比 MCMC 更快找到最高點，或是在限定的總爬山次數中找到比較高的山頭。


演化算法在實務上很有效，但也面臨了一些理論上的嚴重考驗：雖然名為「指引」，但實際上到目前都卻無法有數學上的證明這個「指引」的過程如何發生，甚至無法證明這個指引的存在。也因此，這個領域在實務上廣為應用，但在計算理論上卻還沒有辦法獲得所有人的認同。

這也是現今科學遇到的一個瓶頸：我們還沒有完整的數學及邏輯架構來詮釋並分析非線性的現象。目前少數可用的工具，都是建立在量子力學的方法上，利用大量反覆的實驗，來描繪出非線性的現象，但是距離「解釋」這些現象，則還有很長的路要走。